package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/3/25.
 * 给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。
 */
public class TestProblem18 {

    /**
     * 根据给定的要删除的节点，可以直接找到其后年的节点，把后面的节点的内容复制到当前节点处，
     * 同时将当前节点指向其后面节点的后面节点保证链表不断开，再把下一节点删掉就相当于把给定的节点删除了。
     */

    /**
     * 构造一个链表
     */
    public static class ListNode {
        public int data;
        public ListNode next;
        public ListNode (int data,ListNode next) {
            this.data = data;
            this.next = next;
        }
    }

    /**
     * 删除节点 要考虑链表中是否只有一个节点(即是头(尾)节点),删除的话要置头为null
     * @param head
     * @param node
     */
    public static void deleteNode (ListNode head,ListNode node) {
        //删除尾节点，采用顺序查找找到尾节点的前一节点
        if (node.next == null) {
            while (head.next != node) {
                head = head.next;
            }
            head.next = null;
        }
        //要删除的节点是头结点
        else if (head == node){
            head = null;
        }
        //要删除的节点是中间的普通节点
        else {
            node.data = node.next.data;
            node.next = node.next.next;
        }



    }


}
